package practise.alogrithm.hundredInterviewQuestions;

import practise.alogrithm.hundredInterviewQuestions.Utils.TreeNode;

import javax.xml.soap.Node;
import java.util.ArrayList;
import java.util.List;

/**
 * get all the path, in which the nodes sum equals to the input, this is for the path from root to leaf, not the path in the middle
 */
public class SumPathInTree {
    TreeNode treeNode;
    public SumPathInTree(TreeNode treeNode){
        this.treeNode = treeNode;
    }
    public List<List<TreeNode>> getSumPath(int sum){
        List<List<TreeNode>> result = new ArrayList<>();
         getSumPathFromTree(sum,treeNode,result);
        return result;
    }

    private void getSumPathFromTree(int sum, TreeNode treeNode,List<List<TreeNode>> result){
        if(treeNode.getLeft()==null && treeNode.getRight()==null){// we are reaching the leaf
            if(sum==treeNode.getValue()){
                if(result==null){
                    result = new ArrayList<>();
                }
                List<TreeNode> path = new ArrayList<>();
                path.add(treeNode);
                result.add(path);
            }
        }
        getSumPathFromTree(sum-treeNode.getValue(),treeNode.getLeft(),result);
        getSumPathFromTree(sum-treeNode.getValue(),treeNode.getRight(),result);
        if(result!=null){
            for(List<TreeNode> path:result){
                path.add(treeNode);
            }
        }
    }
}
